#lang racket
(define (abs x)
  (if (> x 0) x (- x)))
(define (square x) (* x x))
(define (average x y) (/ (+ x y) 2))
(define (sqrt x)
  (letrec (
           [good-enough? (λ (guess)
                               (< (abs (- (square guess) x)) 0.00001))]
           [improve (λ (guess)
                         (average guess (/ x guess)))]
           [sqrt-iter (λ (guess)
                           (if (good-enough? guess)
                                  guess
                                  (sqrt-iter (improve guess))))])
    (sqrt-iter 1.0)))

(define (inc i) (+ i 1))
(define (dec i) (- i 1))

;; factorial by recurisiv
(define (fact-rec n)
  (if (= n 1) 1
     (* n (fact-rec (dec n)))))

;; factorial by iteration
(define (fact-iter n)
  (define (fact-inner-iter i prod)
    (if (> i n) prod
       (fact-inner-iter (inc i) (* i prod))))
  (fact-inner-iter 1 1))

(define (fib n)
  (if (<= n 1) n
     (+ (fib (- n 1)) (fib (- n 2)))))

(define (fib2 n)
  (define (fib-iter i r1 r2)
    (cond
      [(= i n) (+ r1 r2)]
      (else (fib-iter (inc i) r2 (+ r1 r2)))))
  (if (<= n 1) n
     (fib-iter 2 0 1)))

(define (pow x n)
  (cond
    [(= n 0) 1]
    [(even? n) (square (pow x (/ n 2)))]
    (else (* x (pow x (- n 1))))))

(define (is_prime x)
  (define (is_prime_iter n x)
    (cond
      [(> (square n) x) #t]
      [(= (remainder x n) 0) #f]
      [else (is_prime_iter (+ n 2) x)]))
  (cond
    [(< x 2) #f]
    [(= x 2) #t]
    [(even? x) #f]
    [else (is_prime_iter 3 x)]))

;; pow(a,n) % b
(define (rem a n b)
  (cond [(= n 1)   (remainder a b)]
        [(even? n) (remainder (square (rem a (/ n 2) b)) b)]
        (else (remainder (* a (rem a (- n 1) b)) b))))

(define (maybe-prime x)
  (cond
    [(< x 10000) (is_prime x)]
    (else (and (= 1 (rem (- x 1) x x))
               (= 1 (rem (/ x 2) x x))))))
